#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

/*
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() == 0 || nums.size() == 1) {
            return 0;
        }
        if (nums.size() == 2) {
            return nums[1] - nums[0];
        }
        sort(nums.begin(), nums.end());
        int output = 0;
        for (int i = 0, length = nums.size() - 1; i < length; i++) {
            int distance = nums[i + 1] - nums[i];
            output = max(output, distance);
        }
        return output;
    }
};
*/

class Solution {
private:
    struct box {
        int min = INT32_MAX;
        int max = INT32_MIN;
        bool is_empty = true;
    };
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() == 0 || nums.size() == 1) {
            return 0;
        }
        if (nums.size() == 2) {
            return nums[1] - nums[0];
        }
        int min = INT32_MAX;
        int max = INT32_MIN;
        for (int num : nums) {
            min = std::min(min, num);
            max = std::max(max, num);
        }
        int box_num = nums.size() - 1;
        int box_range = (int) ceil((float) (max - min - 1) / (float) box_num);
        if (box_range == 0) {
            return 0;
        }
        vector<box> boxes(box_num);
        for (int num : nums) {
            int index = (num - 1 - min) / box_range;
            if (index >= (int) boxes.size()) {
                index = boxes.size() - 1;
            } else if (index < 0) {
                index = 0;
            }
            boxes[index].min = std::min(boxes[index].min, num);
            boxes[index].max = std::max(boxes[index].max, num);
            boxes[index].is_empty = false;
        }
        int output = 0;
        for (int i = 0, length = boxes.size() - 1; i < length; ) {
            if (boxes[i].is_empty) {
                i = i + 1;
                continue;
            }
            int next_i = i + 1;
            while (boxes[next_i].is_empty) {
                next_i++;
                if (next_i >= boxes.size()) {
                    return output;
                }
            }
            output = std::max(output, boxes[next_i].min - boxes[i].max);
            i = next_i;
        }
        return output;
    }
};

int main() {
    vector<int> input = {1, 1, 1, 1, 1, 5, 5, 5, 5, 5};
    Solution solution;
    int output = solution.maximumGap(input);
    cout << output << endl;
    return 0;
}
